package cn.xdf.learn.leetcode.贪心算法;


import java.util.Arrays;


public class MoneyPay {

    public static void main(String[] args) {
        System.out.println(payMoney(348));
    }



    /**
     * 钱币找零问题 这是生活中很常见的问题,
     * 你的钱包中有1元,5元,10元,50元,100元,分别为a1张,a2张,a3张,a4张,a5张,你需要用这些钱去支付y元,至少需要多少张纸币.
     * 贪心算法来计算的话,很明显,每一次用最大面额的纸钞即可.
     */
    public static int payMoney(int money) {
        int n = 5;
        //定义钱数与张数
        int count[] = {5, 3, 3, 4, 10};
        int value[] = {1, 5, 10, 50, 100};

        int num = 0;
        for (int i = n - 1; i >= 0; i--) {
            //金额面值
            int v = value[i];
            //金额张数
            int countNum = count[i];
            //需要张数
            int c = Math.min(money / v, countNum);
            //剩余要分配的钱
            money = money - c * v;
            //累加张数
            num += c;
        }
        return num;

    }


    /**
     * LeetCode 455.Assign Cookies
     * 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，
     * 这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，
     * 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
     *
     * 作者：爱西考的王同学
     * 链接：https://juejin.cn/post/6844904128011993102
     * 来源：稀土掘金
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param ch
     * @param co
     * @return
     */
    public static int distributeCookies(int[] ch,int[] co){
        Arrays.sort(ch);
        Arrays.sort(co);
        int gi = 0;
        int sj = 0;
        while (sj <= co.length & gi <= ch.length){
            if (ch[gi] <= co[sj]){
                gi++;
            }
            sj++;
        }
        return gi;
    }


}
